package 中等;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class n数之和 {

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        System.out.println(fourSum(nums,0));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        return threeSum(nums,0,-2 );
    }

    public static List<List<Integer>> threeSum(int[] nums,int start,int target) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        int n = start;
        while (n<len){
            int i = n+1;
            int j =len-1;
            int res = target - nums[n];
            while (i < j){
                int sum = nums[i] + nums[j];
                if (sum > res){
                    while (j > i && nums[j] == nums[j-1]){
                        j--;
                    }
                    j--;
                }else if (sum < res){
                    while (i < j && nums[i] == nums[i+1]){
                        i++;
                    }
                    i++;
                }else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[n]);
                    list.add(nums[i]);
                    list.add(nums[j]);
                    lists.add(list);
                    while (j > i && nums[j] == nums[j-1]){
                        j--;
                    }
                    j--;
                    while (i < j && nums[i] == nums[i+1]){
                        i++;
                    }
                    i++;
                }
            }
            while (n< len-1 && nums[n] == nums[n+1]){
                n++;
            }
            n++;
        }
        return lists;
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        int start = 0;
        while (start < len){
            int n = start+1;
            while (n<len){
                int i = n+1;
                int j =len-1;
                int res = target - nums[start] - nums[n];
                while (i < j){
                    int sum = nums[i] + nums[j];
                    if (sum > res){
                        while (j > i && nums[j] == nums[j-1]){
                            j--;
                        }
                        j--;
                    }else if (sum < res){
                        while (i < j && nums[i] == nums[i+1]){
                            i++;
                        }
                        i++;
                    }else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[start]);
                        list.add(nums[n]);
                        list.add(nums[i]);
                        list.add(nums[j]);
                        lists.add(list);
                        while (j > i && nums[j] == nums[j-1]){
                            j--;
                        }
                        j--;
                        while (i < j && nums[i] == nums[i+1]){
                            i++;
                        }
                        i++;
                    }
                }
                while (n< len-1 && nums[n] == nums[n+1]){
                    n++;
                }
                n++;
            }
            while (start < len-1 && nums[start] == nums[start+1]){
                start++;
            }
            start++;
        }
        return lists;
    }
}
